home *** CD-ROM | disk | FTP | other *** search
/ Suzy B Software 2 / Suzy B Software CD-ROM 2 (1994).iso / extras / programm / a56 / src / keybld.c < prev    next >
C/C++ Source or Header  |  1995-04-27  |  4KB  |  231 lines
  1. /*
  2.  * Copyright (C) 1990-1994 Quinn C. Jensen
  3.  *
  4.  * Permission to use, copy, modify, distribute, and sell this software
  5.  * and its documentation for any purpose is hereby granted without fee,
  6.  * provided that the above copyright notice appear in all copies and
  7.  * that both that copyright notice and this permission notice appear
  8.  * in supporting documentation.  The author makes no representations
  9.  * about the suitability of this software for any purpose.  It is
  10.  * provided "as is" without express or implied warranty.
  11.  *
  12.  */
  13. static char *Copyright = "Copyright (C) 1990-1994 Quinn C. Jensen";
  14.  
  15. /*
  16.  * keybld - builds a finite-state parser for the given keyword list
  17.  *
  18.  */
  19.  
  20. #include <stdio.h>
  21. #include "a56.h"
  22.  
  23. char buf[1024];
  24.  
  25. main()
  26. {
  27.     int line = 0;
  28.  
  29.     while(gets(buf)) {
  30.         char *bp = buf;
  31.         line++;
  32.         while(*bp != '\t' && *bp != ' ') bp++;
  33.         *bp++ = '\0';
  34.         while(*bp == '\t' || *bp == ' ') bp++;
  35.         if(strcmp(buf, ".code") == 0) {
  36.             printf("%s\n", bp);
  37.         } else if(add_tok(buf, bp) == -1) {
  38.             fprintf(stderr, "input line %d: ambiguous\n", line);
  39.         }
  40.     }
  41.  
  42.     dump_machine();
  43.     return 0;
  44. }
  45.  
  46. #define MAX_CHAR 'z'
  47.  
  48. #define TRANSITIONS (MAX_CHAR + 1)
  49.  
  50. struct state {
  51.     int number;
  52.     char *seen;
  53.     struct trans {
  54.         char action;
  55.         void *arg;
  56.     } trans[TRANSITIONS];
  57.     struct state *next;
  58. } empty_state, *stop = NULL, *scur = NULL, *new_state();
  59. int n_states = 0;
  60.  
  61. /* actions */
  62. #define NOMATCH 0    /* argument is nothing */
  63. #define GOTO 1        /* argument is target state */
  64. #define TERMINAL 2    /* argument is which user action to perform */
  65.  
  66. struct user_action {
  67.     char *action;
  68.     struct user_action *next;
  69. } *utop = NULL, *ucur = NULL;
  70. int n_user_actions = 0;
  71.  
  72. add_tok(tok, actions)
  73. char *tok, *actions;
  74. {
  75.     struct state *scur;
  76.     struct user_action *unew = (struct user_action *)alloc(sizeof *unew);
  77.     unew->action = strsave(actions);
  78.     unew->next = NULL;
  79.     if(ucur)
  80.         ucur->next = unew;
  81.     ucur = unew;
  82.     if(utop == NULL)
  83.         utop = unew;
  84.  
  85.     if(stop == NULL)
  86.         new_state(NULL);
  87.  
  88.     if(follow(*tok, tok + 1, stop) == -1)
  89.         return -1;
  90.  
  91.     n_user_actions++;
  92.     return 0;
  93. }
  94.  
  95. follow(c, tp, sp)
  96. char c;
  97. char *tp;
  98. struct state *sp;
  99. {
  100.     struct trans *arcp, *arcup;
  101.     
  102.     if(c >= 'a' && c <= 'z') {
  103.         c -= 'a' - 'A';
  104.     }
  105.     arcp = sp->trans + c;
  106.  
  107.     if(c >= 'A' && c <= 'Z') {
  108.         arcup = sp->trans + c + 'a' - 'A';
  109.     } else {
  110.         arcup = arcp;
  111.     }
  112.  
  113.     if(c == '\0') {
  114.         if(arcp->action == TERMINAL) {
  115.             return -1;
  116.         } else {
  117.             arcp->action = arcup->action = TERMINAL;
  118.             arcp->arg = arcup->arg = (void *)n_user_actions;
  119.             return 0;
  120.         }
  121.     } else {
  122.         if(arcp->action == GOTO) {
  123.             return follow(*tp, tp + 1, arcp->arg);
  124.         } else {
  125.             struct state *new = new_state(tp);
  126.             arcp->action = arcup->action = GOTO;
  127.             arcp->arg = arcup->arg = (void *)new;
  128.             return follow(*tp, tp + 1, new);
  129.         }
  130.     }
  131. }
  132.  
  133. struct state *new_state(tp)
  134. char *tp;
  135. {
  136.     struct state *snew = (struct state *)alloc(sizeof *snew);
  137.     char tmp[1024];
  138.  
  139.     *snew = empty_state;
  140.  
  141.     snew->number = n_states++;
  142.  
  143.     snew->next = NULL;
  144.  
  145.     if(scur)
  146.         scur->next = snew;
  147.     scur = snew;
  148.  
  149.     if(stop == NULL)
  150.         stop = snew;
  151.  
  152.     if(tp)
  153.         strncpy(tmp, buf, tp - buf);
  154.     else
  155.         strcpy(tmp, "<nothing>");
  156.  
  157.     snew->seen = strsave(tmp);
  158.  
  159.     return snew;
  160. }
  161.  
  162. dump_machine()
  163. {
  164.     struct state *sp;
  165.     struct user_action *up;
  166.     int n, a;
  167.  
  168.     printf("/* state machine generated by keybld */\n");
  169.     printf("/* states=%d actions=%d */\n", n_states, n_user_actions);
  170.     printf("/* %d bytes required for transition table storage */\n",
  171.         sizeof(short) * TRANSITIONS * n_states);
  172.  
  173.     printf("short transitions[%d][%d] = {\n", n_states, TRANSITIONS);
  174.     for(n = 0, sp = stop; sp; sp = sp->next, n++) {
  175.         printf("    /* state %d: \"%s\" */\n", n, sp->seen);
  176.         printf("    {");
  177.         for(a = 0; a < TRANSITIONS; a++) {
  178.             struct trans *tp = sp->trans + a;
  179.             switch(tp->action) {
  180.             case GOTO:
  181.                 printf("%d", ((struct state *)tp->arg)->number);
  182.                 break;
  183.             case TERMINAL:
  184.                 printf("%d", -(int)tp->arg - 1);
  185.                 break;
  186.             case NOMATCH:
  187.                 printf("0");
  188.                 break;
  189.             }
  190.             printf(",%s", a % 20 == 19 ? "\n\t\t" : "");
  191.         };
  192.         printf("},\n");
  193.     }
  194.  
  195.     printf("};\n");
  196.  
  197.     printf("\
  198. \n\
  199. kparse(kp)\n\
  200. char *kp;\n\
  201. {\n\
  202.     int state = 0;\n\
  203. \n\
  204.     for(;;) {\n\
  205.         short transition = transitions[state][*kp];\n");
  206.  
  207. printf("\
  208.         if(transition == 0) {\n\
  209.             return 0;\n\
  210.         } else if(transition > 0) {\n\
  211.             kp++;\n\
  212.             state = transition;\n\
  213.         } else {\n\
  214.             switch(-transition) {\n");
  215.  
  216.     for(n = 1, up = utop; up; up = up->next, n++) {
  217.         printf("\
  218.             case %d:\n\
  219.                 %s;\n\
  220.                 break;\n", n, up->action);
  221.     }
  222.  
  223.     printf("\
  224.             }\n\
  225.             return transition;\n\
  226.         }\n\
  227.     }\n\
  228. }\n");
  229.  
  230. }
  231.